package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/sort-colors/
 *  2,0,2,1,1,0   a one-pass algorithm using only O(1) constant space?
 * @author tzp
 * @since 2020/10/18
 */
public class LC75 implements TwoProblem {

    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int pivot01 = -1, pivot12 = nums.length, i = 0;
        while (i < nums.length && i < pivot12) {
            if (nums[i] == 0) {
                pivot01++;
                nums[i] = nums[pivot01];
                nums[pivot01] = 0;//swap
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                pivot12--;
                nums[i] = nums[pivot12];
                nums[pivot12] = 2;//swap
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 0, 2, 1, 1, 0};
        new LC75().sortColors(a);
        System.out.println(Arrays.toString(a));
    }
}
